package top.lcm889.nowcoder.top;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @author Coder-lcm
 * @date 2021/4/1
 */
public class NC119_最小的K个数 {
    public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
        int len = input.length;
        if (k > len) {
            return new ArrayList<>();
        }
        // PriorityQueue默认是小顶堆（即堆顶元素是最小的），改写比较器可以让其成为大顶堆
        PriorityQueue<Integer> MaxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer integer, Integer t1) {
                return t1 - integer;
            }
        });
        for (int i = 0; i < len; i++) {
            if (MaxHeap.size() < k) {
                MaxHeap.add(input[i]);
            }else {
                if (MaxHeap.peek() > input[i]) {
                    MaxHeap.poll();
                    MaxHeap.add(input[i]);
                }
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            res.add(MaxHeap.poll());
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(GetLeastNumbers_Solution(new int[]{12,33,434,54,67,8,34,66}, 3));
    }

}
